package bit.training.week1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.ceil;

public class week1 {


    /**
     * 滑动窗口
     * https://ac.nowcoder.com/acm/problem/221681
     * 解决问题：解决数组、字符串的连续子区间问题
     * 使用条件：每个值都大于0（满足单调性）
     */
    /**
     * 下面使用scanner速度太慢了，所以采用自定义的方式重新输入
     */
    public static void movingWindow() throws IOException {

        //Scanner in = new Scanner(System.in);
        Read in = new Read();
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int x = in.nextInt();
        int []a=new int [n+1];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
        }
        int l=1,r=1;//遍历的左右下标
        int best_l=1;int best_r=1;int min_len=n;
        int sum=0;
        while(r<=n){
            sum+=a[r];
            while(sum>=x){
                if(r-l+1<min_len){
                    min_len=r-l+1;
                    best_l=l;
                    best_r=r;
                }
                sum-=a[l++];
            }
            r++;
        }
        System.out.println(best_l+" "+best_r);
    }

    static class Read{
        StringTokenizer st=new StringTokenizer("");
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        // 3. 补全 next() 方法：读取一行数据并分割成 token
        String next() throws IOException {
            // 如果当前 token 用完了，读取下一行并重新分割
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }

        // 4. 补全 nextInt() 方法：调用 next() 并转成整数
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    /**
     * 牛牛的快递
     * https://www.nowcoder.com/practice/41b42e7b3c3547e3acf8e90c41d98270?tpId=290&tqId=39852&ru=/exam/oj
     */
    public static void test1(){

        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextFloat()) { // 注意 while 处理多个 case
            float a = in.nextFloat();

            char b = in.next().charAt(0);
            int result = check(a, b);
            System.out.println(result);
        }
    }
    public static int check(float a, char b) {
        if (a < 1) {//不足一千克
            //加急
            if (b == 'y') {
                return 25;
            }
            //不加急
            else if (b == 'n') {
                return 20;
            }
        } else {//超过1千克
            float remain = a - 1;
            int s = (int)ceil( remain );
            int k = 0;
            if (b == 'y') {
                k = 5;
            } else if (b == 'n') {
                k = 0;
            }
            s = s + k + 20;
            return s;
        }
        return -1;//处理无效输入
    }


    /**
     * 数组中两个字符串的最小距离（模拟+贪心）
     * https://www.nowcoder.com/questionTerminal/2c6a0a8e1d20492f92941400036e0890
     */
    public static void test2(){

        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        //思路：遍历数组，找出两个字符串第一次出现时的位置，用一个变量记录两个位置之间的距离
        //随着下标变化，如果距离变短了，就更新
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int index1=-1,index2=-1;
            //经过尝试，0x3f3f3f3f 因为满足 “足够大、不溢出、易初始化” 的核心需求，被越来越多选手采用；
            //随着竞赛教程、题解的传播，这个数逐渐成为编程领域的 “常识”，尤其在处理数组初始化、最小 / 最大值计算时，成为默认选择。
            int wid=0x3f3f3f3f;//距离
            int n=in.nextInt();
            String[]str;//两个待查找的数组
            in.nextLine();//吸收空格
            str=in.nextLine().split(" ");
            String str1=str[0];
            String str2=str[1];
            if(str1==null||str2==null){
                System.out.println(-1);
                continue;
            }
            String []strs=new String[n];//输入目标数组（最长的那个）
            for(int i=0;i<n;i++){
                strs[i]=in.nextLine();
            }
            //遍历求距离
            for(int i=0;i<n;i++){
                if(str1.equals(strs[i])){
                    index1=i;
                    if(index2!=-1){
                        wid=Math.min(Math.abs(i-index2),wid);
                    }
                }
                if(str2.equals(strs[i])){
                    index2=i;
                    if(index1!=-1){
                        wid=Math.min(Math.abs(i-index1),wid);
                    }
                }
            }
            if(index1==-1||index2==-1){
                System.out.println(-1);
                continue;
            }
            System.out.println(wid);

        }
    }

    /**
     * 除以2
     * https://ac.nowcoder.com/acm/problem/213140
     */
    public static void test3_1(){
        /**
         * 做法一：普通思路，没有使用堆，超时了
         */
        //输入
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int []a=new int [n+1];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
        }
        //业务逻辑
        int sum=0;
        for(int i=0;i<k;i++){//外层循环：次数
            Boolean flg=false;
            int j=1;int max_j=0; int max=0;
            for( j=1;j<=n;j++){//内存循环：数组
                if(a[j]%2!=0){//只操作偶数
                    continue;
                }
                if(a[j]>max){
                    max=a[j];
                    max_j=j;
                }
                if(max==0){//没有最大的数
                    flg=true;
                    break;
                }
            }
            a[max_j]=max/2;
            //已经找到了最大的数
            if(flg==true)//如果所有数都等于0，直接结束循环
            {
                break;
            }
        }
        for(int i=1;i<=n;i++){
            sum+=a[i];
        }
        System.out.println(sum);
    }

    /**
     * 除以2
     * 使用堆来处理大量的数据，不会超时
     */
    public static void test3_2(){
        //使用堆的版本
        /**
         * 失败的代码使用了int类型存储总和sum和输入数据x，而通过的代码使用了long类型：
         * 当输入数据较大（例如超过int的最大值2^31-1）时，int类型会发生溢出，导致计算结果错误。
         * 题目中没有限制数据范围，使用int必然会在大数据测试用例中失败，而long能处理更大的数值范围。
         */
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        //构建最大堆
        //Greater greater=new Greater();
//        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(greater);
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->{
            return b-a;
        });
        long sum=0,x;
        for(int i=0;i<n;i++){//循环结束就自动计算总和
            x=in.nextLong();
            if(x%2==0){
                priorityQueue.offer((int)x);//输入的数据直接存进堆里
            }

            sum=sum+x;
        }
        for(int i=0;i<k;i++){
            if(priorityQueue.isEmpty()){
                break;
            }
            int num=(int)priorityQueue.poll()/2;
            sum=sum-num;
            if(num%2==0){
                priorityQueue.offer(num);
            }
        }
        System.out.println(sum);
    }

//    static class Greater implements Comparator<Integer> {
//        @Override
//        public int compare(Integer o1, Integer o2) {
//            return o2-o1;//构建大根堆
//        }
//    }

    /**
     * 斐波那契额数列
     * https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=122&tqId=33668&ru=/exam/oj
     */
    public static void fibonacci(){
        int []F=new int [100];
        F[0]=0;F[1]=1;
        for(int i=2;i<100;i++){
            F[i]=F[i-1]+F[i-2];
        }
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=in.nextInt();
        Boolean flg=true;
        int left_ans=n,right_ans=n;
        int count=0;
        while(flg==true){
            for(int i=0;i<100;i++){
                if(left_ans==F[i]||right_ans==F[i]){
                    flg=false;
                    break;
                }
            }
            left_ans--;
            right_ans++;
            count++;
        }

        System.out.println(count-1);

    }

    public static void fibonacci2(){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int a=0,b=1,c=a+b;
        while(n>c){
            a=b;
            b=c;
            c=a+b;
        }
        System.out.println(Math.min(n-b,c-n));
    }

    /**
     * 单词搜索
     * https://www.nowcoder.com/practice/987f2981769048abaf6180ed63266bb2?tpId=196&tqId=39583&ru=/exam/oj
     * 深度优先算法
     */
    //上下左右
    int []dx={0,0,-1,1};
    int []dy={-1,1,0,0};
    boolean vis[][];
    char[]word;
    int m,n;

    public boolean exist (String[] board, String _word) {
        // write code here
        word=_word.toCharArray();
        m=board.length; n=board[0].length();
        vis=new boolean[m][n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i].charAt(j)==word[0]){
                    if(dfs(board,i,j,0)==true){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    //深度优先算法
    public boolean dfs(String[]board,int i,int j,int pos){
        if(pos==word.length-1){
            return true;
        }
        vis[i][j]=true;
        for(int k=0;k<4;k++){
            int x=i+dx[k];
            int y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&board[x].charAt(y)==word[pos+1]){
                if(dfs(board,x,y,pos+1)){
                    return true;
                }
            }
        }
        vis[i][j]=false;
        return false;
    }

    /**
     * 杨辉三角
     * https://www.nowcoder.com/practice/e671c6a913d448318a49be87850adbcc?tpId=290&tqId=39928&ru=/exam/oj
     */
    public static void yanghui(){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();

        List<List<Integer>>arr=new ArrayList<>();
        List<Integer>pre=new ArrayList<>();
        for(int i=0;i<n;i++){
            List<Integer> line=new ArrayList<>();
            if(i>0){
                pre=arr.get(i-1);
                line.add(1);
                for(int j=1;j<i;j++){
                    line.add(pre.get(j-1)+pre.get(j));
                }
            }
            line.add(1);
            arr.add(line);
        }
        for(int i=0;i<n;i++){
            for(int num:arr.get(i)){
                System.out.printf("%5d",num);
            }
            System.out.println();
        }
    }

    /**
     * you的加分
     * https://www.nowcoder.com/questionTerminal/cd117803b3364b218a8b3dcc498dee25
     */
    public static void count_you(){
        Scanner sc=new Scanner(System.in);
        int q=sc.nextInt();
        int a,b,c;
        int ret=0;
        while(q-->0) {
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            ret = you(a, b, c);
            System.out.println(ret);
        }
    }
    //a:y   b:o    c:u
    public static int you(int a,int b,int c){
        int p=0;
        int min=Math.min(a,Math.min(b,c));
        p=2*min;
        a-=min;b-=min;c-=min;
        while(b>=2){
            p+=1;
            b-=1;
        }
        return p;
    }

    /**
     * 腐烂的苹果（多源BFS）
     * https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34?tpId=196&tqId=40529&ru=/exam/oj
     * @param grid
     * @return
     */
    public int rotApple(ArrayList<ArrayList<Integer>> grid){
        int m = grid.size();
        int n = grid.get(0).size();
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid.get(i).get(j) == 2)
                {
                    q.add(new int[]{i, j});
                }
            }
        }
        int ret = 0;
        while(!q.isEmpty())
        {
            int sz = q.size();
            while(sz-- != 0)
            {
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for(int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false
                            && grid.get(x).get(y) == 1)
                    {
                        vis[x][y] = true;
                        q.add(new int[]{x, y});
                    }
                }
            }
            ret++;
        }
        // 判断剩余的苹果
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid.get(i).get(j) == 1 && !vis[i][j])
                {
                    return -1;
                }
            }
        }
        return ret - 1;
    }



    
    public static void main(String[] args) {

    }







}
